home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / littlest / littl-st.lha / memory.c < prev    next >
C/C++ Source or Header  |  1993-08-10  |  10KB  |  451 lines
  1. /*
  2.     Little Smalltalk, version 2
  3.     Written by Tim Budd, Oregon State University, July 1987
  4.  
  5.     Improved incorporating suggestions by 
  6.         Steve Crawley, Cambridge University, October 1987
  7.         Steven Pemberton, CWI, Amsterdam, Oct 1987
  8.  
  9.     memory management module
  10.  
  11.     This is a rather simple, straightforward, reference counting scheme.
  12.     There are no provisions for detecting cycles, nor any attempt made
  13.     at compaction.  Free lists of various sizes are maintained.
  14.     At present only objects up to 255 bytes can be allocated, 
  15.     which mostly only limits the size of method (in text) you can create.
  16.  
  17.     reference counts are not stored as part of an object image, but
  18.     are instead recreated when the object is read back in.
  19.     This is accomplished using a mark-sweep algorithm, similar
  20.     to those used in garbage collection.
  21.  
  22. */
  23.  
  24. # include <stdio.h>
  25.  
  26. # ifdef LIGHTC
  27. # include <unix.h>
  28. # include <storage.h>
  29. # include <proto.h>
  30. # endif
  31.  
  32. # include "env.h"
  33. # include "memory.h"
  34.  
  35. # ifdef STRING
  36. # include <string.h>
  37. # endif
  38. # ifdef STRINGS
  39. # include <strings.h>
  40. # endif
  41.  
  42. # ifdef ALLOC
  43. # include <alloc.h>
  44. # endif
  45. # ifndef ALLOC
  46. extern char *calloc();
  47. # endif
  48.  
  49. boolean debugging = false;
  50. object sysobj;    /* temporary used to avoid rereference in macros */
  51. object intobj;
  52.  
  53. object symbols;        /* table of all symbols created */
  54.  
  55. /*
  56.     in theory the objectTable should only be accessible to the memory
  57.     manager.  Indeed, given the right macro definitions, this can be
  58.     made so.  Never the less, for efficiency sake some of the macros
  59.     can also be defined to access the object table directly
  60.  
  61.     Some systems (e.g. the Macintosh) have static limits (e.g. 32K)
  62.     which prevent the object table from being declared.
  63.     In this case the object table must first be allocated via
  64.     calloc during the initialization of the memory manager.
  65. */
  66.  
  67. # ifdef obtalloc
  68. struct objectStruct *objectTable;
  69. # endif
  70. # ifndef obtalloc
  71. struct objectStruct objectTable[ObjectTableMax];
  72. # endif
  73.  
  74. /*
  75.     The following variables are strictly local to the memory
  76.     manager module
  77.  
  78.     FREELISTMAX defines the maximum size of any object.
  79. */
  80.  
  81. # define FREELISTMAX 2000
  82. static object objectFreeList[FREELISTMAX];/* free list of objects */
  83.  
  84. # ifndef mBlockAlloc
  85.  
  86. # define MemoryBlockSize 6000
  87.         /* the current memory block being hacked up */
  88. static object *memoryBlock;        /* malloc'ed chunck of memory */
  89. static int    currentMemoryPosition;    /* last used position in above */
  90. # endif
  91.  
  92.  
  93. /* initialize the memory management module */
  94. noreturn initMemoryManager() {
  95.     int i;
  96.  
  97. # ifdef obtalloc
  98.     objectTable = obtalloc(ObjectTableMax, sizeof(struct objectStruct));
  99.     if (! objectTable)
  100.         sysError("cannot allocate","object table");
  101. # endif
  102.  
  103.     /* set all the free list pointers to zero */
  104.     for (i = 0; i < FREELISTMAX; i++)
  105.         objectFreeList[i] = nilobj;
  106.  
  107.     /* set all the reference counts to zero */
  108.     for (i = 0; i < ObjectTableMax; i++) {
  109.         objectTable[i].referenceCount = 0;
  110.         objectTable[i].size = 0;
  111.         }
  112.  
  113.     /* make up the initial free lists */
  114.     setFreeLists();
  115.  
  116. # ifndef mBlockAlloc
  117.     /* force an allocation on first object assignment */
  118.     currentMemoryPosition = MemoryBlockSize + 1;
  119. # endif
  120.  
  121.     /* object at location 0 is the nil object, so give it nonzero ref */
  122.     objectTable[0].referenceCount = 1;
  123.     objectTable[0].size = 0;
  124. }
  125.  
  126. /* setFreeLists - initialise the free lists */
  127. setFreeLists() {
  128.     int i, size;
  129.     register int z;
  130.     register struct objectStruct *p;
  131.  
  132.     objectFreeList[0] = nilobj;
  133.  
  134.     for (z=ObjectTableMax-1; z>0; z--) {
  135.         if (objectTable[z].referenceCount == 0){
  136.             /* Unreferenced, so do a sort of sysDecr: */
  137.             p= &objectTable[z];
  138.             size = p->size;
  139.             if (size < 0) size = ((-size) + 1)/2;
  140.             p->class = objectFreeList[size];
  141.             objectFreeList[size]= z;
  142.             for (i= size; i>0; )
  143.                 p->memory[--i] = nilobj;
  144.             }
  145.         }
  146. }
  147.  
  148. /*
  149.   mBlockAlloc - rip out a block (array) of object of the given size from
  150.     the current malloc block 
  151. */
  152. # ifndef mBlockAlloc
  153.  
  154. object *mBlockAlloc(memorySize)
  155. int memorySize;
  156. {    object *objptr;
  157.  
  158.     if (currentMemoryPosition + memorySize >= MemoryBlockSize) {
  159.         
  160.         /* we toss away space here.  Space-Frugal users may want to
  161.         fix this by making a new object of size
  162.         MemoryBlockSize - currentMemoryPositon - 1
  163.         and putting it on the free list, but I think
  164.         the savings is potentially small */
  165.  
  166.         memoryBlock = (object *) calloc((unsigned) MemoryBlockSize, sizeof(object));
  167.         if (! memoryBlock)
  168.             sysError("out of memory","malloc failed");
  169.         currentMemoryPosition = 0;
  170.         }
  171.     objptr = (object *) &memoryBlock[currentMemoryPosition];
  172.     currentMemoryPosition += memorySize;
  173.     return(objptr);
  174. }
  175. # endif
  176.  
  177. /* allocate a new memory object */
  178. object allocObject(memorySize)
  179. int memorySize;
  180. {    int i;
  181.     register int position;
  182.     boolean done;
  183.  
  184.     if (memorySize >= FREELISTMAX) {
  185.         fprintf(stderr,"size %d\n", memorySize);
  186.         sysError("allocation bigger than permitted","allocObject");
  187.         }
  188.  
  189.     /* first try the free lists, this is fastest */
  190.     if ((position = objectFreeList[memorySize]) != 0) {
  191.         objectFreeList[memorySize] = objectTable[position].class;
  192.         }
  193.  
  194.     /* if not there, next try making a size zero object and
  195.         making it bigger */
  196.     else if ((position = objectFreeList[0]) != 0) {
  197.         objectFreeList[0] = objectTable[position].class;
  198.         objectTable[position].size = memorySize;
  199.         objectTable[position].memory = mBlockAlloc(memorySize);
  200.         }
  201.  
  202.     else {        /* not found, must work a bit harder */
  203.         done = false;
  204.  
  205.         /* first try making a bigger object smaller */
  206.         for (i = memorySize + 1; i < FREELISTMAX; i++)
  207.             if ((position = objectFreeList[i]) != 0) {
  208.                 objectFreeList[i] = objectTable[position].class;
  209.                 /* just trim it a bit */
  210.                 objectTable[position].size = memorySize;
  211.                 done = true;
  212.                 break;
  213.                 }
  214.  
  215.         /* next try making a smaller object bigger */
  216.         if (! done)
  217.             for (i = 1; i < memorySize; i++)
  218.                 if ((position = objectFreeList[i]) != 0) {
  219.                     objectFreeList[i] =
  220.                         objectTable[position].class;
  221.                     objectTable[position].size = memorySize;
  222. # ifdef mBlockAlloc
  223.                     free(objectTable[position].memory);
  224. # endif
  225.                     objectTable[position].memory = 
  226.                         mBlockAlloc(memorySize);
  227.                     done = true;
  228.                     break;
  229.                     }
  230.  
  231.         /* if we STILL don't have it then there is nothing */
  232.         /* more we can do */
  233.         if (! done)
  234.             sysError("out of objects","alloc");
  235.         }
  236.  
  237.     /* set class and type */
  238.     objectTable[position].referenceCount = 0;
  239.     objectTable[position].class = nilobj;
  240.     objectTable[position].size = memorySize;
  241.     return(position << 1);
  242. }
  243.  
  244. object allocByte(size)
  245. int size;
  246. {    object newObj;
  247.  
  248.     newObj = allocObject((size + 1) / 2);
  249.     /* negative size fields indicate bit objects */
  250.     sizeField(newObj) = - size;
  251.     return newObj;
  252. }
  253.  
  254. object allocStr(str)
  255. register char *str;
  256. {    register object newSym;
  257.  
  258.     newSym = allocByte(1 + strlen(str));
  259.     ignore strcpy(charPtr(newSym), str);
  260.     return(newSym);
  261. }
  262.  
  263. # ifdef incr
  264. object incrobj;        /* buffer for increment macro */
  265. # endif
  266. # ifndef incr
  267. void incr(z)
  268. object z;
  269. {
  270.     if (z && ! isInteger(z)) {
  271.         objectTable[z>>1].referenceCount++;
  272.         }
  273. }
  274. # endif
  275.  
  276. # ifndef decr
  277. void decr(z)
  278. object z;
  279. {
  280.     if (z && ! isInteger(z)) {
  281.         if (--objectTable[z>>1].referenceCount <= 0) {
  282.             sysDecr(z);
  283.             }
  284.         }
  285. }
  286. # endif
  287.  
  288. /* do the real work in the decr procedure */
  289. sysDecr(z)
  290. object z;
  291. {    register struct objectStruct *p;
  292.     register int i;
  293.     int size;
  294.  
  295.     p = &objectTable[z>>1];
  296.     if (p->referenceCount < 0) {
  297.         fprintf(stderr,"object %d\n", z);
  298.         sysError("negative reference count","");
  299.         }
  300.     decr(p->class);
  301.     size = p->size;
  302.     if (size < 0) size = ((- size) + 1) /2;
  303.     p->class = objectFreeList[size];
  304.     objectFreeList[size] = z>>1;
  305.     if (size > 0) {
  306.         if (p->size > 0)
  307.             for (i = size; i; )
  308.                 decr(p->memory[--i]);
  309.         for (i = size; i > 0; )
  310.             p->memory[--i] = nilobj;
  311.         }
  312.     p->size = size;
  313. }
  314.  
  315. # ifndef basicAt
  316. object basicAt(z, i)
  317. object z;
  318. register int i;
  319. {
  320.     if (isInteger(z))
  321.         sysError("attempt to index","into integer");
  322.     else if ((i <= 0) || (i > sizeField(z))) {
  323.         ignore fprintf(stderr,"index %d size %d\n", i, (int) sizeField(z));
  324.         sysError("index out of range","in basicAt");
  325.         }
  326.     else
  327.         return(sysMemPtr(z)[i-1]);
  328.     return(0);
  329. }
  330. # endif
  331.  
  332. # ifndef simpleAtPut
  333.  
  334. void simpleAtPut(z, i, v)
  335. object z, v;
  336. int i;
  337. {
  338.     if (isInteger(z))
  339.         sysError("assigning index to","integer value");
  340.     else if ((i <= 0) || (i > sizeField(z))) {
  341.         ignore fprintf(stderr,"index %d size %d\n", i, (int) sizeField(z));
  342.         sysError("index out of range","in basicAtPut");
  343.         }
  344.     else {
  345.         sysMemPtr(z)[i-1] = v;
  346.         }
  347. }
  348. # endif
  349.  
  350. # ifndef basicAtPut
  351.  
  352. void basicAtPut(z, i, v)
  353. object z, v;
  354. register int i;
  355. {
  356.     simpleAtPut(z, i, v); 
  357.     incr(v);
  358. }
  359. # endif
  360.  
  361. # ifdef fieldAtPut
  362. int f_i;
  363. # endif
  364.  
  365. # ifndef fieldAtPut
  366. void fieldAtPut(z, i, v)
  367. object z, v;
  368. register int i;
  369. {
  370.     decr(basicAt(z, i)); basicAtPut(z, i, v);
  371. }
  372. # endif
  373.  
  374. # ifndef byteAt
  375. int byteAt(z, i)
  376. object z;
  377. register int i;
  378. {    byte *bp;
  379.     unsigned char t;
  380.  
  381.     if (isInteger(z))
  382.         sysError("indexing integer","byteAt");
  383.     else if ((i <= 0) || (i > 2 * - sizeField(z))) {
  384.         fprintf(stderr,"index %d size %d\n", i, sizeField(z));
  385.         sysError("index out of range","byteAt");
  386.         }
  387.     else {
  388.         bp = bytePtr(z);
  389.         t = bp[i-1];
  390. fprintf(stderr,"byte at %d returning %d\n", i, (int) t);
  391.         i = (int) t;
  392.         }
  393.     return(i);
  394. }
  395. # endif
  396.  
  397. # ifndef byteAtPut
  398. void byteAtPut(z, i, x)
  399. object z;
  400. int i, x;
  401. {    byte *bp;
  402.  
  403.     if (isInteger(z))
  404.         sysError("indexing integer","byteAtPut");
  405.     else if ((i <= 0) || (i > 2 * - sizeField(z))) {
  406. fprintf(stderr,"index %d size %d\n", i, sizeField(z));
  407.         sysError("index out of range", "byteAtPut");
  408.         }
  409.     else {
  410.         bp = bytePtr(z);
  411.         bp[i-1] = x;
  412.         }
  413. }
  414. # endif
  415.  
  416. /*
  417. Written by Steven Pemberton:
  418. The following routine assures that objects read in are really referenced,
  419. eliminating junk that may be in the object file but not referenced.
  420. It is essentially a marking garbage collector algorithm using the 
  421. reference counts as the mark
  422. */
  423.  
  424. visit(x)
  425. register object x;
  426. {
  427.     int i, s;
  428.     object *p;
  429.  
  430.     if (x && !isInteger(x)) {
  431.         if (++(objectTable[x>>1].referenceCount) == 1) {
  432.             /* then it's the first time we've visited it, so: */
  433.             visit(objectTable[x>>1].class);
  434.             s = sizeField(x);
  435.             if (s>0) {
  436.                 p = objectTable[x>>1].memory;
  437.                 for (i=s; i; --i) visit(*p++);
  438.                 }
  439.             }
  440.         }
  441. }
  442.  
  443. int objectCount()
  444. {    register int i, j;
  445.     j = 0;
  446.     for (i = 0; i < ObjectTableMax; i++)
  447.         if (objectTable[i].referenceCount > 0)
  448.             j++;
  449.     return j;
  450. }
  451.